package C056;

/**
 * ClassName: c03
 * Package: C056
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/4/25 10:06
 * @Version 1.0
 * @Since 1.0
 */
public class c03 {
    public static void main(String[] args) {
        String[] arr = {"tars","rats","arts","star"};
        System.out.println(numSimilarGroups(arr));
    }

    static int MAXLEN = 300;
    static int[] father = new int[MAXLEN];
    static int[] stack = new int[MAXLEN];
    static int sets;

    public static int numSimilarGroups(String[] strs) {
        int strlen = strs[0].length();
        int n = strs.length;
        build(n);
        int diff = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if(find(i) != find(j)) {
                    diff = 0;
                    for (int k = 0; k < strlen && diff < 3; k++) {
                        if(strs[j].charAt(k) != strs[i].charAt(k)) {
                            diff ++;
                        }
                    }
                    if(diff == 0 || diff == 2) {
                        // 合并两个
                        union(i, j);
                    }
                }
            }
        }
        return sets;
    }

    private static void union(int i, int j) {
        int fatheri = find(i);
        int fatherj = find(j);
        if(fatheri == fatherj) {
            return;
        }
        father[fatherj] = fatheri;
        sets --;
    }

    private static void build(int n) {
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
        sets = n;
    }

    private static int find(int i) {
        int size = 0;
        while(i != father[i]) {
            stack[size ++] = i;
            i = father[i];
        }

        // 扁平化
        while(size > 0) {
            father[stack[-- size]] = i;
        }
        return i;
    }
}
